package arithmetic.fibonacci;

/**
 * Created by jiangfeng on 2017/10/12.
 * // 斐波那契数列非递归实现，递归实现效率太低
 */
public class Fibonacci {
    public static void main(String args[]) {
        for (int i = 1; i < 100; i++) {
            System.out.println(fib(i));
        }

    }


    public static int fib(int n) {
        if(n<2) {
            return n;
        }
        int a =0,b =1,r =1;
        for(int i =2;i<n;i++){
            a = b;
            b = r;
            r = a+b;
        }
        return r;
    }

    /**
     * 循环实现
     * @param n
     * @return
     */
    public static long fibonacci(long n){
        int prePreResult=0,preResult=1,result=1;
        while (n>2){
            prePreResult = preResult;
            preResult = result;
            result = prePreResult + preResult;
            n--;
        }
        return result;
    }

    /**
     * 递归实现 就超级慢，因为重复计算
     * 在递归计算Fibonacci(10)时，Fibonacci(3)的值被计算了21次。而在递归计算Fibonacci(30)，这个调用的次数是骇人的317811次！
     * @param n
     * @return
     */
    public static long fibonacci2(long n){
        if(n<2)return 1;
        return fibonacci2(n-2)+fibonacci2(n-1);
    }

}
